package _go

/*46. 全排列
难度
中等

1309

收藏

分享
切换为英文
接收动态
反馈
给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]
*/
/*多叉树的深度遍历过程就是回溯算法*/
var res [][]int

func permute(nums []int) [][]int {
	if nums == nil {
		return nil
	}
	res = [][]int{}
	dfs(nums, 0, []int{}, map[int]int{}, &res)
	return res
}

/*
   dept 表示深度
   path 表示路径
   use 表示已经使用的数
   res 返回结果

	有两个大坑  1  需要地址引用才能正确的保存结果值
			  2 需要切片复制才能保存正确的路径 因为切片是公用内存的
*/
func dfs(nums []int, dept int, path []int, use map[int]int, res *[][]int) {
	//结束条件
	if len(nums) == dept {
		tmp := make([]int, dept)
		copy(tmp, path)
		*res = append(*res, tmp)
		// fmt.Printf("res %v \n",res)
		return
	}

	for _, v := range nums {
		if use[v] != 1 {
			//选择一个
			path = append(path, v)
			use[v] = 1

			//选择下一个
			dfs(nums, dept+1, path, use, res)

			//回溯
			path = path[:len(path)-1]
			use[v] = 0
		}
	}
}
